МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ТЕСТУВАННЯ ЧИСЕЛ НА ПРОСТОТУ ТА ПОБУДОВА ДОВГИХ ПРОСТИХ ЧИСЕЛ. ФАКТОРИЗАЦІЯ СКЛАДЕНИХ ЧИСЕЛ.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 3
З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ”
для студентів базових напрямів
6.170101 “Безпека інформаційних і комунікаційних систем”,
6.170102 “Системи технічного захисту інформації”,
6.170103 “Управління інформаційною безпекою”
Затверджено на засiданнi кафедри “Захист інформації”,
протокол № від 2008 р.
Львів – 2008
Тестування чисел на простоту та побудова довгих простих чисел. Факторизація складених чисел: Методичні вказівки до лабораторної роботи №3 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с.
Укладачі: А.Е.Лагун, к.т.н., доцент
В.М.Іванюк, асистент
Відповідальний за випуск:
І.Я. Тишик, старший викладач.
Рецензент: В.В.Максимович, д.т.н., професор.
ЛАБОРАТОРНА РОБОТА №3
І. Тестування чисел на простоту і побудова великих простих чисел
Мета роботи
Засвоїти основні програмні методи тестування чисел на простоту.
Вказівки до роботи
Ознайомитися з лекційним матеріалом, а також з літературою [2], [8], [14] – [16], [18].
6.1. Метод пробних ділень
Якщо - складне, тоді , де причому . Тому для ми перевіряємо чи ділиться на ? Якщо дільник числа не буде знайдений, тоді – просте. В іншому випадку буде знайдено мінімальний простий дільник числа , тобто ми навіть розкладемо на два множника. Складність методу складає арифметичних операцій з цілими числами.
Можливі модифікації цього методу. Наприклад, ми можемо перевірити чи ділиться на 2 і на 3, і якщо ні, то перебираємо далі тільки числа виду .
6.2. Решето Ератосфена
Якщо ми хочемо скласти таблицю всіх простих чисел серед чисел 2, 3, ..., тоді необхідно спочатку викреслити всі числа, які діляться на 2, крім 2. Потім взяти число 3 і викреслити всі наступні числа, які діляться на 3. Потім взяти наступне не викреслене число (тобто 5) і викреслити всі наступні числа, які діляться на нього і так далі. В результаті залишаться лише прості числа.
Для реалізації методу необхідний великий об’єм пам’яті ЕОМ, але для складання таблиць простих чисел він є найкращим.
Всього необхідно арифметичних операцій.
6.3. Критерій Вільсона
Теорема 1.
Для будь-якого наступні умови еквівалентні:
– просте;
Даний критерій інколи буває зручним в доказах, але застосовувати його для перевірки простоти неможливо через складність.
6.4. Тест на основі малої теореми Ферма
Мала теорема Ферма стверджує, що якщо – просте, тоді виконується умова: можливе порівняння:
(1)
Обернене твердження хибне.
З цієї теореми випливає, що якщо (1) не виконалося хоча б для одного числа а в інтервалі , тоді – складне. Тому можна запропонувати наступний ймовірнісний тест простоти:
Вибираємо випадкове число з інтервалу і перевіряємо за допомогою алгоритму Евкліда умову .
Перевіряємо виконуваність порівняння .
Якщо порівняння (1) не виконано, то відповідь - складне.
Якщо порівняння (1) виконано, тоді відповідь невідома, але можна повторити тест ще раз.
Якщо виконується порівняння (1), то говорять, що число є псевдопростим відносно . Відзначимо, що існує безкінечно багато пар чисел , де - складне і псевдопросте відносно . Наприклад, при отримуємо , хоча .
Особливий випадок складають складні числа, для яких умова порівняння виконується при всіх основах. Вони називаються псевдопростими числами, або числами Кармайкла.
Таким чином, при застосуванні описаного вище тесту може виникнути три ситуації:
число просте і тест завжди говорить «не відомо»;
число складне і не є числом Кармайкла; тоді з ймовірністю успіху не менше тест дає відповідь « - складне»;
число складне і є числом Кармайкла, тоді ...
